#ifndef RTREE_HPP
#define RTREE_HPP

#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include "utils.hpp"

#define MAX 3 ///Número máximo de entradas em um nó
#define MIN 1 ///Número minimo de entradas em um nó
#define P 2	///Numero de elemento removidos no reinsert
#define DIM 3 ///Dimensão dos pontos

enum TipoReinsercao{
    FAR_REINSERT,
    CLOSE_REINSERT
};

///Classes definida em utils.hpp
class BoundingBox;
class Ponto;

class No;

class Entrada{
	public:
		virtual ~Entrada(){};
};

class EntradaInterna: public Entrada{
    public:
        BoundingBox *bb;
        No *filho;
        EntradaInterna(No* filho);
		virtual ~EntradaInterna();
};

class EntradaFolha: public Entrada{
    public:
        Ponto *p;
		EntradaFolha(Ponto *p);
		virtual ~EntradaFolha();
		void print();
};

class No{
    private:
        int tamanho; ///Entradas ocupadas

	protected:
		bool eFolha; ///É folha?
		bool filhoFolha; ///Aponta para folhas?
		bool overflow; ///Já teve algum overflow?
        bool eRaiz; ///É raiz?
        No(bool eFolha, bool filhoFolha, bool eRaiz, int altura);

	public:
        Entrada **entradas;
        int altura; ///Em que altura está. A mais alta é a raiz.
        No();
        ~No();
        bool getEFolha();
        int getTamanho();
        void decrementaTamanho();
		void incrementaTamanho();
		void print(int pai, int altura);

		///Retorna área de sobreposição de bb(que representa a entrada de indice pos)
		///e as bbs de todas as outras entradas do nó.
		///Apenas para nó interno.
		float sobreposicao(
            BoundingBox *bb,    ///@in bb de pos
            int pos);           ///@in indice da entrada do nó representada por bb

        ///Retorna nó filho que tem menor incremento de sobreposição com as outras bb quando inserir ponto
        ///e o indice k na entrada do nivel superior.
        ///Apenas para nó interno.
		No* menorIncSobreposicao(
            Ponto *ponto,   ///@in ponto que será inserido
            int *k,         ///@out indice da entrada
            bool teste);

        ///Retorna nó filho que tem menor incremento de area quando inserir ponto
        ///e o indice k na entrada do nivel superior
        ///Apenas para nó interno.
		No* menorIncArea(
            Ponto *ponto,   ///@in ponto que será inserido
            int *k);        ///@out indice da entrada

        ///Retorna caminho para inserir ponto
		void escolherSubarvore(
            No *raiz,       ///@in raiz da árvore
            Ponto *ponto,   ///@in ponto que será inserido
            No** caminho,   ///@out caminho a partir da raiz até o nó folha que englobará ponto
            int *tamanho,   ///@out tamanho do caminho
            int **k,        ///@out indice das entradas para encontrar cada nó filho. k[tamanho-1]=-1.
            bool teste);

        ///Remove e reinsere P entradas do nó.
        ///Apenas para nó folha.
		void reinsercao(
            BoundingBox *bb,    ///@in bb do nó.
            No *raiz,           ///@in raiz da árvore.
            Ponto *p,           ///@in ponto que causou overflow
            Ponto **removidos); ///@out pontos a serem removidos

        ///Divide o nó em dois conjuntos.
        ///Apenas para nó folha.
		No* divisao(
            No *raiz,   ///@in raiz da árvore.
            Ponto *p);  ///@in ponto que causou overflow

        bool insereEntrada(
            No **raiz,
            No **caminho,
            int tamanho,
            EntradaInterna *e);

        ///Inserir ponto na árvore
		bool insere(
            No **raiz,              ///@in raiz da árvore
            Ponto *ponto,           ///@in ponto a ser inserido
            TipoReinsercao tipo,    ///@in Tipo de reinserção.
            bool teste);

        void Contador(bool *k);
};

///Calcula margem das possiveis divisões da distribuição de pontos pos
///e altera distMin e margem mínima se a margem for menor.
void valorMargem(
    float coordenadas[], ///@in Valores mínimos ou máximos de todos os pontos em um determinado eixo
    int pos[], ///@in Distribuição dos pontos
    int distMin[], ///@out Distribuição de margem mínima
    int tamanho, ///@in tamanho de coordenadas, pos e distMin = número de pontos considerados
    float *margemMinima); ///@in/@out Atual margem mínima/Margem mínima encontrada.

///Calcula sobreposição das possíveis divisões de distMin.
///Retorna posição da quebra: inicio do conjunto 2.
int minSobreposicao(
    EntradaFolha **entradas, ///Entradas que serão divididas.
    int distMin[], ///Distribuição das entradas em determinado eixo.
    int tamanho); ///Tamanho de entradas e distMin.

#endif // RTREE_HPP
